package java_thinking.unit_16.source;

import java.util.Arrays;

/**
 * @Desc:   三分单向扫描
 * @author: cww
 * @DateTime: 2019-04-23 23:40
 */

public class Div3ScanSort {
    public static void main(String[] args) {
        int[] a1 = {5,4,1,1,2,9,8,1,3,5,15,22,1,8};
        div3ScanSort(a1);
        System.out.println(Arrays.toString(a1));
    }

    public static void div3ScanSort(int[] items) {
        div3ScanSort(items, 0, items.length -1);
    }

    /**
     * 单向扫描,双向靠拢
     * 将序列划分为3段：小于pivot的元素，等于pivot的元素，大于pivot的元素
     * @param items
     * @param start
     * @param end
     */
    public static void div3ScanSort(int[] items, int start, int end) {
        if (start < end) {
            int pivot = items[start];
            int i = start, j = end, k = start + 1;
            OUT_LOOP : while (k < j) {
                if (items[k] < pivot) {
                    swap(items, i, k);
                    i++;
                    k++;
                } else if (items[k] == pivot) {
                    k++;
                } else {
                    while (items[j] > pivot) {
                        j--;
                        if (k > j) {
                            // 扫描终止
                            break OUT_LOOP;
                        }
                    }
                    if (items[j] < pivot) {
                        swap(items, k, j);
                        swap(items, i, k);
                    } else {
                        swap(items, k, j);
                    }
                    k++;
                }
            }
            div3ScanSort(items, start, i - 1);
            div3ScanSort(items, j+1, end);
        }
    }


    public static void swap(int[] items, int i, int j) {
        int tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }
}
